1. Technical Field
The invention is related to computers for use robotics in which most computations involve vectors in Euclidian space and transformation matrices therefore. In particular, the invention is related to computers whose architecture is reconfigurable among a plurality of processor elements.
2. Background of the Invention
Two classes of computation-intensive problems can be distinguished in robotics applications. The first comprises the rather specific kinematics and dynamics problems required for real-time control, simulation, dynamic trajectory generation and path planning.
Inadequate computing power has always been the major obstacle in real-time implementation of advanced robotic schemes, due to the computational cost of the evaluation of required kinematic and dynamic models. Dynamic simulation of the robot arm requires even more computing power than does control. The problem becomes more difficult for direct-drive arms, representing even faster dynamics, and for redundant and multiple arms, which involve more degrees of freedom. Fast dynamic trajectory generation and path planning demand even far more computing power. It is widely recognized that parallel computing is the key to achieving required computing power for real-time robotic control and simulation.
The second class comprises more generic problems which require even more computation power. This second class of problems includes, for example, low level image processing, graphics display, tactile sensory processing, singular value decomposition for inverse kinematic solution of redundant arms. Therefore, computer designs for robotic application should address these two different classes of problems.
The first need is to develop a highly parallel architecture for a class of specific problems in robotics, namely kinematics and dynamics. The second need is to address the second class of problems, which require more generality and flexibility while preserving the high performance which existing parallel architectures fail to address adequately. The common features of the problems in this class are determinacy in the computing locality for communication, and the existence of fine grain parallelism.
Theoretical analyses have shown that systolic and wave front processor arrays can be used efficiently for a wide class of problems with the above-listed properties. The main advantage of systolic and wave front arrays is their capability of combining pipeline and parallel processing. This is an important feature, since in many problems pipelining presents the only opportunity of concurrent processing. Another advantages of these systolic and wave front arrays is their ability to overlap the input/output operations and computation. However, two main problems arise in practical implementation of systolic and wave front processor arrays:
1) The gap between memory and processor speed: Performance analysis of systolic and wave front arrays is based on the assumptions that parallel memory modules are available, that data are already aligned, and that data can be fed into the array with adequate speed. In practice, satisfying these assumptions, particularly for large and two-dimensional arrays, is difficult, and the resulting overhead can undermine performance. Note that these architectures are basically attached processors, and data are provided by a host processor. Therefore, data are basically provided in serial form. PA1 2) Rigidity: In systolic arrays, unless the individual cells are programmable, maximum flexibility cannot be achieved. Lack of reconfigurability in the interconnect structure among the cells is another source of rigidity, since achieving maximum efficiency for different problems requires the capability of providing different interconnection structures. However, due to practical problems such as clock distribution, even for arrays with static interconnections, practical implementations have been confined to one-dimensional arrays.
It is an object of the invention to implement an architecture capable of achieving the efficiency and generality of systolic arrays, by overcoming the foregoing difficulties.